//输入一个字符串，打印出该字符串中字符的所有排列。
//
//
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
//
//
//
// 示例:
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
//
//
//
//
// 限制：
//
// 1 <= s 的长度 <= 8
//
// Related Topics 字符串 回溯 👍 683 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function permutation(s: string): string[] {


    function backtracking(temp) {
        if (temp.length === s.length) {
            resArr.add([...temp].join(''))
            return
        }
        for (let i = 0; i < s.length; i ++) {
            if (set.has(i)) continue
            temp.push(s[i])
            set.set(i,1)
            backtracking(temp)
            temp.pop()
            set.delete(i)
        }
    }
    let resArr : Set<string> = new Set<string>()
    let set = new Map()
    backtracking([])
    return Array.from(resArr)
};
//leetcode submit region end(Prohibit modification and deletion)
//? visit数组记录
function permutation2(s: string): string[] {
    const rec = [], vis = [];
    const n = s.length;
    const arr = Array.from(s).sort();
    const perm = [];
    const backtrack = (arr, i, n, perm) => {
        if (i === n) {
            rec.push(perm.toString());
            return;
        }
        for (let j = 0; j < n; j++) {
            //? 访问过/前面有重复元素
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] === arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.push(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.pop();
            vis[j] = false;
        }
    }

    backtrack(arr, 0, n, perm);
    const size = rec.length;
    const recArr = new Array(size).fill(0);
    for (let i = 0; i < size; i++) {
        recArr[i] = rec[i].split(',').join('');
    }
    return recArr;
};
